//
// Created by Administrator on 2021/4/8.
//

/*
给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。

百度百科中最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”


示例 1：
输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
输出：3
解释：节点 5 和节点 1 的最近公共祖先是节点 3 。

示例 2：
输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
输出：5
解释：节点 5 和节点 4 的最近公共祖先是节点 5 。因为根据定义最近公共祖先节点可以为节点本身。

示例 3：
输入：root = [1,2], p = 1, q = 2
输出：1

提示：
树中节点数目在范围 [2, 105] 内。
-109 <= Node.val <= 109
所有 Node.val 互不相同 。
p != q
p 和 q 均存在于给定的二叉树中。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-tree
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。*/

#include <iostream>
#include <unordered_map>

using namespace std;

// Definition for a binary tree node.
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;

    explicit TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}

    TreeNode(int x, TreeNode *l, TreeNode *r) : val(x), left(l), right(r) {}
};

class Solution {
private:
    TreeNode *ans;
public:
    // 判断root是否是p q 的最近祖先
    bool commonFather(TreeNode *root, TreeNode *p, TreeNode *q) {
        if (root == nullptr) return false; // 空节点
        bool inLeft = commonFather(root->left, p, q); // 递归 判断左子树中有没有 p or q
        bool inRight = commonFather(root->right, p, q);// 递归 判断右子树中有没有p or q
        // 左右同时满足，则必定是一边p 一边q （各个元素不相同）
        // 如果该节点正好为p 或者 q 则只需要左子树或者右子树满足
        if ((inLeft and inRight) or ((root->val == p->val || root->val == q->val) and (inLeft or inRight)))
            ans = root;    // 符合最近祖先的定义，更改ans
        return inLeft or inRight or root->val == p->val or root->val == q->val; // 当前树的子数有没有p or q
    }

    TreeNode *lowestCommonAncestor(TreeNode *root, TreeNode *p, TreeNode *q) {
        commonFather(root, p, q);
        return ans;
    }

};


class Solution2 { // 题解 递归
    TreeNode *ans;
public:
    bool dfs(TreeNode *root, TreeNode *p, TreeNode *q) {
        if (root == nullptr) return false;
        bool lson = dfs(root->left, p, q); // 左子树中有没有p 或 q
        bool rson = dfs(root->right, p, q);// 右子树中有没有p 或 q
        if ((lson && rson) || ((root->val == p->val || root->val == q->val) && (lson || rson))) {
            ans = root;
        }
        return lson || rson || root->val == p->val || root->val == q->val;
    }

    TreeNode *lowestCommonAncestor(TreeNode *root, TreeNode *p, TreeNode *q) {
        dfs(root, p, q);
        return ans;
    }
};

class Solution3 {  // 题解 hash储存父节点信息
public:
    unordered_map<int, TreeNode *> father; // hash 父节点信息
    unordered_map<int, bool> visited; // hash 节点是否被访问过
    // dfs 遍历树 储存每个节点的父节点信息
    void dfs(TreeNode *root) {
        if (root->left != nullptr) {
            father[root->left->val] = root;
            dfs(root->left);
        }
        if (root->right != nullptr) {
            father[root->right->val] = root;
            dfs(root->right);
        }
    }

    TreeNode *lowestCommonAncestor(TreeNode *root, TreeNode *p, TreeNode *q) {
        father[root->val] = nullptr;  // 根节点父节点为空
        dfs(root); // 遍历得到所有节点的父节点信息
        // 找p的父节点链
        while (p != nullptr) {
            visited[p->val] = true;
            p = father[p->val];
        }
        // 找q的父节点链，如果某个父节点已经被p给访问过，则就是最近的公共祖先节点
        while (q != nullptr) {
            if (visited[q->val]) return q;
            q = father[q->val];
        }
        return nullptr;
    }
};

int main() {
    auto t9 = TreeNode(4);
    auto t8 = TreeNode(7);
    auto t7 = TreeNode(8);
    auto t6 = TreeNode(0);
    auto t5 = TreeNode(2, &t8, &t9);
    auto t4 = TreeNode(6);
    auto t3 = TreeNode(1, &t6, &t7);
    auto t2 = TreeNode(5, &t4, &t5);
    auto t1 = TreeNode(3, &t2, &t3);
    Solution3 sol{};
    auto ans = sol.lowestCommonAncestor(&t1, &t7, &t6);
    cout << ans->val;
    return 0;
}